Cos'è crivello di eratostene?

Il crivello di Eratostene è un metodo antico ed efficiente per trovare tutti i numeri primi fino a un determinato numero N. Questo algoritmo si basa sull'idea di eliminare i multipli di ciascun numero primo trovato, partendo dal numero 2.

Il crivello di Eratostene prende il nome dal matematico greco Eratostene di Cirene che lo descrisse per la prima volta nel III secolo a.C.

Il funzionamento del crivello di Eratostene è il seguente:

1. Si crea un elenco di numeri da 2 a N.
2. Si parte dal primo numero primo, che è il 2, e si eliminano tutti i suoi multipli dalla lista.
3. Si passa al successivo numero primo nella lista e si eliminano i suoi multipli.
4. Si procede in questo modo fino ad arrivare a N.
5. I numeri rimasti dopo questo processo sono tutti primi.

Il crivello di Eratostene è un algoritmo molto efficiente per trovare numeri primi in intervalli relativamente piccoli. Tuttavia, per numeri molto grandi, l'algoritmo può diventare computazionalmente costoso e si preferiscono altri metodi più efficienti, come i test di primalità basati su algoritmi più avanzati.